// // https://www.lintcode.com/problem/word-search-ii/description


// MLE,用字典构建树，而不是矩阵！！！这样用trie也没什么好处了
// class TrieNode {
// public:
//     TrieNode** children;
//     TrieNode ()
//     {
//         children = new TrieNode*[26];
//         for (int i = 0; i < 26; ++i) {
//             children[i] = NULL; //注意初始化!!!
//         }
//     }
// };

// class Solution {
// public:
//     /**
//      * @param board: A list of lists of character
//      * @param words: A list of string
//      * @return: A list of string
//      */
//     TrieNode* root;
//     int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
//     bool search(string s) {
//         TrieNode* tmp = root;
//         for (int i = 0; i < s.length(); ++i) {
//             if (!tmp->children[s[i] - 'a']) {
//                 return false;
//             }
//             tmp = tmp->children[s[i] - 'a'];
//         }
//         return true;
//     }
//     bool check(int i, int j, vector<vector<char>> &board) {
//         int n = board.size(); 
//         int m = board[0].size();
//         return i >= 0 && i < n && j >= 0 && j < m;
//     }
//     void build(TrieNode * node, int x, int y, vector<vector<char>> &board, vector<vector<bool>> &visited) 
//     {
//         if (!check(x, y, board) || visited[x][y]) {
//             return;
//         }
//         visited[x][y] = true;
//         if (!node->children[board[x][y] - 'a'])
//             node->children[board[x][y] - 'a'] = new TrieNode;
//         node = node->children[board[x][y] - 'a'];
//         for (int i = 0; i < 4; ++i) {
//             int newX = x + dir[i][0];
//             int newY = y + dir[i][1];
            
//             build(node, newX, newY, board, visited);
//         }
//         visited[x][y] = false;
//     }
   
//     vector<string> wordSearchII(vector<vector<char>> &board, vector<string> &words) {
//         int n = board.size();
//         int m = board[0].size();
//         root = new TrieNode; //别忘了初始化!!!
//         vector<string> res;
//             // vector<vector<bool>> visited(n, vector<bool>(m, false));
//         for (int i = 0; i < n; ++i) {
//             for (int j = 0; j < m; ++j) {
//                 // if (bfs(board, words[w], 0, i, j, visited)) {
//                     // res.push_back(words[w]);   
//                 // }
//                 vector<vector<bool>> visited(n, vector<bool>(m, false));
//                 build(root, i, j, board, visited);
//             }
//         }
//         for (int w = 0; w < words.size(); ++w)
//         {
//             string s = words[w];
//             if (search(s)) {
//                 res.push_back(s);
//             }
//         }
//         return res;
//     }
// };



// https://www.lintcode.com/problem/word-search-ii/description
// Trie用来剪枝

class TrieNode {
public:
    map<char, TrieNode*> children;
    //如果字母表大，什么都可能用到，用哈希表；基本都是26个则用数组（哈希表存取还是比数组慢）
    string word = "";
    TrieNode ()
    {
    }
};
class Trie {
public:
    TrieNode* root;
    Trie() {
        root = new TrieNode;
    }
    void insert(string word) {
        TrieNode* tmp = root;
        for (int i = 0; i < word.size(); ++i) {
            // if ((tmp->children).find(word[i] - 'a') == (tmp->children).end()) {
                // tmp->children[word[i] - 'a'] = new TrieNode;
            // }
            // tmp = tmp->children[word[i] - 'a'];
            if ((tmp->children).find(word[i]) == (tmp->children).end()) {
                tmp->children[word[i]] = new TrieNode;
            }
            tmp = tmp->children[word[i]];
        }
        tmp->word = word;
    }
};
class Solution {
public:
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    bool check(int i, int j, vector<vector<char>> &board) {
        int n = board.size(); 
        int m = board[0].size();
        return i >= 0 && i < n && j >= 0 && j < m && board[i][j] != 0;
    }
    
    void search(vector<vector<char>> &board, int x, int y, TrieNode* node, vector<string>&res) {
        if (!check(x, y, board)) {
            return;
        }
        if ((node->children).find(board[x][y]) == (node->children).end()) {
            return;
        }
        node = node->children[board[x][y]];
        if (node->word != "") {
            if (find(res.begin(), res.end(), node->word) == res.end()) { //注意！
                res.push_back(node->word);
            }
        }
        char tmp = board[x][y];
        board[x][y] = 0;
        for (int i = 0; i < 4; ++i) {
            int newX = x + dir[i][0];
            // int newY = y + dir[i][0];
            int newY = y + dir[i][1];
            search(board, newX, newY, node, res);
        }
        board[x][y] = tmp;
        
    }
   
   
   
    vector<string> wordSearchII(vector<vector<char>> &board, vector<string> &words) {
        int n = board.size();
        int m = board[0].size();
        Trie trie;
        vector<string> res;
            // vector<vector<bool>> visited(n, vector<bool>(m, false));
        for (int i = 0; i < words.size(); ++i) {
            trie.insert(words[i]);
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                search(board, i, j, trie.root, res);
            }
        }
        
        return res;
    }
};